export default class KDTree {
    private root: Node;
    private demision: number;
    public leaves: Array<any>;
    constructor(datas: Array<any>, demision: number, getX?: Function, getY?: Function) {
        this.root = new Node(0);
        this.leaves = [];
        this.demision = demision;

        if (!datas || datas.length < 1)
            return;

        let getx = getX ? getX : (d) => { return d['x'] };
        let gety = getY ? getY : (d) => { return d['y'] };

        this.buildTree(datas, getx, gety, this.root);
    }

    private buildTree(datas, getX, getY, node) {
        //处理叶子节点的逻辑
        if (node.depth == this.demision) {
            node.datas = datas;

            if (node.datas && node.datas.length > 0) {
                let maxx = getX(datas[0]);
                let minx = getX(datas[0]);
                let maxy = getY(datas[0]);
                let miny = getY(datas[0]);
                for (let j = 0; j < datas.length; j++) {
                    let data = datas[j];

                    minx = (getX(data) < minx) ? getX(data) : minx;
                    miny = (getY(data) < miny) ? getY(data) : miny;

                    maxx = (getX(data) > maxx) ? getX(data) : maxx;
                    maxy = (getY(data) > maxy) ? getY(data) : maxy;
                }
                node.minx = minx;
                node.maxx = maxx;
                node.miny = miny;
                node.maxy = maxy;

                node.area = (node.maxx - node.minx) * (node.maxy - node.miny);
            }
            else {
                node.area = 0;
            }

            this.leaves.push(node);
            return;
        }

        if (!datas || datas.length < 1)
            return;

        node.left = new Node(node.depth + 1);
        node.right = new Node(node.depth + 1);

        //对数据分别进行x和y值的排序
        let dataSortbyX = datas.sort((a, b) => {
            return getX(a) - getX(b);
        });

        let dataSortbyY = datas.sort((a, b) => {
            return getY(a) - getY(b);
        });


        //计算x和y方向的中位值在整个数值区间内的占比
        let median = Math.floor(datas.length / 2);

        let middleXPercent = Math.abs(getX(dataSortbyX[median]) / (getX(dataSortbyX[dataSortbyX.length - 1]) - getX(dataSortbyX[0])) - 0.5);
        let middleYPercent = Math.abs(getY(dataSortbyY[median]) / (getY(dataSortbyY[dataSortbyY.length - 1]) - getY(dataSortbyY[0])) - 0.5);

        node.minx = getX(dataSortbyX[0]);
        node.maxx = getX(dataSortbyX[dataSortbyX.length - 1]);
        node.miny = getY(dataSortbyY[0]);
        node.maxy = getY(dataSortbyY[dataSortbyY.length - 1]);

        node.area = (node.maxx - node.minx) * (node.maxy - node.miny);

        //根据中位值占比来决定此区间的数值切分方式
        node.sortby = middleXPercent > middleYPercent ? 'y' : 'x';
        if (node.sortby == 'x') {
            this.buildTree(dataSortbyX.slice(0, median), getX, getY, node.left);
            this.buildTree(dataSortbyX.slice(median + 1), getX, getY, node.right);
        }
        else {
            this.buildTree(dataSortbyY.slice(0, median), getX, getY, node.left);
            this.buildTree(dataSortbyY.slice(median + 1), getX, getY, node.right);
        }
    }


}

class Node {
    public depth: number;
    public datas: Array<any>;
    public left: Node;
    public right: Node;
    public sortby: string;
    public minx: number;
    public maxx: number;
    public miny: number;
    public maxy: number;
    public area: number;

    constructor(depth) {
        this.depth = depth;
        this.datas = [];
    }

    public isLeaf() {
        return !this.left && !this.right;
    }
}